This invention relates to the secure transmission of digital data messages and more particularly to a complete substitution permutation circuit and method for use in a digital data enciphering and deciphering circuit.
When data is transmitted by a means that is not secure against interception it is necessary to encipher the data so that if it is intercepted, no useful information can be obtained from it. High security applications have always existed, however, recently industrial espionage has reached major proportions requiring the use of data enciphering. The current trend toward the use of renote access networks for the transmission of data, especially when these networks are carried over vulnerable commercial telephone facilities, has resulted in an increased need for data enciphering. It is possible for an interceptor to employ an expert called a cryptanalyst to break the cipher, and then decipher the intercepted data himself. As cryptanalysts have become better at breaking ciphers, aided by sohpisticated computers, more difficult ciphers have been developed in order to maintain data security. The value of any given data enciphering and deciphering technique is measured by how much effort must be expended in order to break it.
One prior art cipher method is performed by using a table with the alphabet in one column and a scrambled alphabet in another column such that for each letter there is one and only one corresponding letter. The original message which it is desired to encipher, called plaintext, is enciphered by looking each letter up in the table and changing it to the corresponding letter. The result, which is called ciphertext, is no longer meaningful to an ordinary person. The cryptanalyst can easily break this cipher, however, by taking advantage of certain information, e.g., the true identity of letters can be determined by their frequency of occurrence, since the average frequency of occurrence of each letter in the alphabet in ordinary English text is well known.
The use of substitution permutation type networks for enciphering and deciphering is now well known, for example see "Cryptography and Computer Privacy" by Horst Feistel, published in the SCIENTIFIC AMERICAN magazine of May 1973 pages 15 to 23. Substitution permutation networks consist of alternating stages of substitution boxes which perform one to one transformations on small groups of input bits and permutation stages which shuffle or permute the binary data lines. The use of alternating stages of substitution and permutation in the design of an enciphering or deciphering network results in an apparently complex and therefore potentially more secure cipher. In order to further enchance the complexity and security of the cipher it has also been taught in the prior art to use a key which is a digital signal that is often changed, for example by assigning different keys to different users in a system that has multiple users, and that is used to alter the enciphering or deciphering circuit so as to further enhance the cipher. The substitution pemutation cipher described by Feistel, as referred to above, uses the individual bits of the key to select one of two possible circuits for each of the substitution boxes used to construct the substitution stages.
Recently the National Bureau of Standards has chosen a variation of the substitution permutation scheme as the Data Encryption Standard, for example see The Federal Register, Volume 40, Number 52 of Monday March 17, 1975 pages 12134 through 12139. Since the Data Encryption Standard as described above, was proposed it has been criticized by some computer scientists as being too weak for the present level of computer technology. It has been suggested that currently available techniques would allow the cipher to be broken for any given key in an unreasonably short period of time and that the key size should be increased from the currently proposed size of 64 bits to something like 128 bits. An example of such criticism can be found in the article by Whitfield Diffie and Martin E. Helman which appeared in COMPUTER magazine of June 1977 pages 74 to 84.
If the key size is large in a substitution permutation circuit there exists a problem in that it is difficult to insure that for all possible keys the circuit which is configured by applying that key is complete. If for some keys the circuit is incomplete then some bits of the circuit outputs will be dependent only on a subset of the circuit inputs, so that in effect the circuit is a less powerful circuit than it would be expected to be. Many schemes for data encryption that intuitively appear to be complex and difficult to break have unexpected incomplete conditions. Therefore in addition to devising an intuitively complex scheme, which no one is able to prove incomplete, it is desirable to design data encryption circuits such that it can be proved that they meet certain standards, especially in terms of being complete. A data translation circuit is called complete if it implements a function such that every output bit is dependent on all input bits. To state it more formally, a complete data translation circuit is a one to one data translation circuit, i.e. every input combination is translated to one and only one output combination, and in addition satisfies the property that for each combination of one output bit and one input bit a certain input signal combination can be applied to all the input bits such that if only the signal present on the one input bits is changed then the signal present on the one output bit will change. For each combination of one output bit and one input bit that satisfy the above property it is then known that the one output bit is a function of that one input bit. If for a certain output bit the above process is successfully repeated for each input bit then that certain output bit is a function of all input bits. If each output bit is tested and determined to be a function of all input bits then the entire data translation circuit is complete.
Although all complete data translation circuits are one to one data translation circuits, not all one to one data translation circuits are complete data translation circuits. As an example consider the identity circuit, i.e. the circuit which transforms every input signal combination into the same output signal combination. The identity circuits is a one to one data translation circuit and yet it is intuitively clear that it is a terrible data enciphering circuit. In particular, the signal present on each output bit corresponds exactly to the signal present on one input bit and so each output bit is dependent on only one input bit and therefore certainly the identity circuit is incomplete. Many other one to one data transformation circuits are also incomplete, for example in a random sample of one to one data transformation circuits many output bits may be found such that the signal present thereon corresponds exactly either to the signal present on one of the input bits or the compliment thereof. All of the substitution boxes referred to in the example of this invention are complete data translation circuits. Small circuits with only a few inputs and outputs can be easily designed to be complete, for example by exhaustively testing for completeness all one to one functions with the desired number of inputs and outputs or other methods described in the detailed description which follows. It is, however, difficult to apply the same technique or other similar techniques to the design of complete data encryption circuits which have more than a small number of inputs and outputs.
It is an object of this invention to design a substitution permutation type network for enciphering and deciphering digital data by interconnecting a number of small complete circuits, such that the entire circuit is complete for any key which it is used with.